﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <list>

using namespace std;
// 原题连接：https://leetcode.cn/problems/binary-tree-level-order-traversal/
/*
题目描述：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。



示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]


提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
*/

// 开始解题：
// 方法1——队列
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        if (root) {
            q.push(root);
        }
        int levelSize = q.size();
        while (!q.empty()) {
            vector<int> v;
            while (levelSize--) {
                TreeNode* cur = q.front();
                v.push_back(cur->val);
                if (cur->left) {
                    q.push(cur->left);
                }
                if (cur->right) {
                    q.push(cur->right);
                }
                q.pop();
            }
            vv.push_back(v);
            levelSize = q.size();
        }
        return vv;
    }
};


int main() {
    int ar[] = { 0,1, 2, 3, 4,  5, 6, 7, 8, 9 };

    int n = sizeof(ar) / sizeof(int);

    list<int> mylist(ar, ar + n);

    list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);

    reverse(mylist.begin(), pos);

    reverse(pos, mylist.end());

    list<int>::const_reverse_iterator crit = mylist.crbegin();

    while (crit != mylist.crend())

    {

        cout << *crit << " ";

        ++crit;

    }

    cout << endl;
    return 0;
}